//: [Previous](@previous)

/*:
 # 快速排序
 * 最好情况 O(nLogn))
 * 最坏情况 O(n^2))
 * 平均时间复杂度 O(nLogn))
 * 空间复杂度 0(Logn)
 
 1. 先设定一个基数
 2. 遍历数组，把小于该基数的放到一边，大于该基数的放到另一边
 3. 递归的把上步的左分区和右分区按同样操作排序
 
 */

/**
 pivot=3 low->3 high->3
 3 6 5 2 7 9 1 4 3
 
 3=3 high--->4
 
 4>3 high--->1
 
 1<3 low=1 low++->6 high->(1)
 1 6 5 2 7 9 (1) 4 3
 
 6 > 3 high=6 high--->9 low->(6)
 1 (6) 5 2 7 9 6 4 3

 9>3 high--->7
 
 7>3 high-->2
 
 2<3 low=2 low++->5 high->(5)
 1 2 5 (5) 7 9 6 4 3
 
 5 > 3 high=5 high--->(5) low->(5)
 1 2 (5) 5 7 9 6 4 3
 
 low=high
 1 2 3 5 7 9 6 4 3
 
 */

import Foundation

var numbers = [3, 6, 5, 2, 7, 9, 1, 4, 3]
print("排序前 \(numbers)")


func quickSort(_ arr: [Int]) -> [Int] {
    if arr.count < 2 {
        return arr
    }
    
    let pivot = arr[0]
    var low = 0
    var high = arr.count-1
    var nums = arr
    
    while low < high {
        
        while low < high && nums[high] >= pivot {
            high -= 1
        }
        nums[low] = nums[high]
        
        while low < high && nums[low] <= pivot {
            low += 1
        }
        nums[high] = nums[low]
    }
    
    nums[low] = pivot

    let left = Array(nums[0..<low])
    var right: [Int] = []
    if low+1 < nums.count {
        right = Array(nums[low+1..<nums.count])
    }
    var temp: [Int] = []
    temp += quickSort(left)
    temp.append(pivot)
    temp += quickSort(right)
    return temp
}

print("快速排序后 \(quickSort(numbers))")

func quickSort2(_ arr: inout [Int], _ low: Int, _ high: Int) {
    if low < high {
        let mid = partition(arr: &arr, low: low, high: high)
        quickSort2(&arr, low, mid-1)
        quickSort2(&arr, mid+1, high)
    }
}

func partition(arr: inout [Int], low: Int, high: Int) -> Int {
    var low = low
    var high = high
    let pivot = arr[low]
    while low < high {
        
        while low < high && arr[high] >= pivot {
            high -= 1
        }
        arr[low] = arr[high]
        
        while low < high && arr[low] <= pivot {
            low += 1
        }
        arr[high] = arr[low]
    }
    arr[low] = pivot
    return low
}

quickSort2(&numbers, 0, numbers.count-1)
print("快速排序2后 \(numbers)")

//: [Next](@next)
